FM FFM

深入浅出Factorization Machines系列

深入浅出Factorization Machines系列 | Kubi Code’Blog

FM

Factorization Machine(FM)由Steffen Rendle在2010年提出，旨在解决系数数据下的特征组合的问题，目前该系列模型在搜索推荐领域被广泛使用。

一个例子

问题就是需要对电影进行评分(y项)，而x都是特征,其中:

  1. 第一部分蓝色的为当前评分的用户
  2. 第二部分红色的为被评分的电影
  3. 第三部分黄色的为该用户曾经对其他电影的评分情况
  4. 第四部分绿色的为该用户当前评分的月数
  5. 第五部分棕色为该用户最新一次评分的电影

这是一个经典的回归问题，最简单粗暴的方法就先上一个线性回归，其中对于绿色特征处理成binary，这样计算公式就是为


这样可能会过于简单粗暴，按照算法（特征）工程师的套路会对某些特征进行组合，这样为了方便，咱们就给他来一个全组合:

看似问题解决了，但是这样会存在这么几个问题:

  1. 参数空间过大,这里为O(n2)，在处理互联网数据时，特征量级别可能是亿级别的。
  2. 需要人工经验，这里一般会选择某些特征来组合，此时人工/专家经验就会很重要。
  3. 样本量稀疏，实际上那这种方式拿到的特征会是很稀疏的，对于在训练样本中未出现过的组合该模型无能为力。

FM解法

定理：对于一个正定矩阵W，始终存在一个矩阵使得


成立（需要V的维数k足够大）
但是在巨大稀疏矩阵的情况下，当k并不是很大时也可以很接近W，因此可以用

其中这里v为长度k的一个向量,⟨vi,vj⟩表示两个向量的点积，在FM中也称为隐向量,这样就有了FM的式子:

其中<>表示两个向量的点积

直观上看，FM的复杂度是 O(kn2)。但是，通过下列等式，FM的二次项可以化简，其复杂度可以优化到 O(kn)。由此可见，FM可以在线性时间对新样本作出预测。

以下是详细证明过程。

之后采用随机梯度下降SGD（Stochastic Gradient Descent）训练模型参数。那么，模型各个参数的梯度如下:

FM总结

首先是为什么使用向量的点积可以解决以上问题呢？

  1. 参数的数量大幅度缩减，从n×(n−1)/2降低到nk
  2. 隐向量的点积可以表示原本两个毫无相关的参数之间的关系
  3. 可以解决稀疏向量问题，因为每个特征都有一个隐向量，就算是稀疏向量在训练样本没有出现过的组合在预测时也可以进行计算。

扩展

FM与矩阵分解MF与SVM有什么差别呢？

  1. FM是一种比较灵活的模型，通过合适的特征变换方式，FM可以模拟二阶多项式核的SVM模型、MF模型、SVD++模型等。
  2. 相比SVM的二阶多项式核而言，FM在样本稀疏的情况下是有优势的；而且，FM的训练/预测复杂度是线性的，而二项多项式核SVM需要计算核矩阵，核矩阵复杂度就是N平方。
  3. 相比MF而言，我们把MF中每一项的rating分改写为rui∼βu+γi+xTuyi，从此公式中可以看出，这相当于只有两类特征 β 和 γ 的FM模型。对于FM而言，我们可以加任意多的特征，比如user的历史购买平均值，item的历史购买平均值等，但是MF只能局限在两类特征。SVD++与MF类似，在特征的扩展性上都不如FM。

FFM

Field-aware Factorization Machine(FFM) 场感知分解机。

场感知说白了可以理解为分类。通过引入field的概念，FFM把相同性质的特征归于同一个field。比如， “MovieClass = romantic”、“MovieClass = action”这2个特征值都是代表电影分类的，可以放到同一个field中。简单来说，同一个类别的特征经过One-Hot编码生成的数值特征都可以放到同一个field。

在FFM中，每一维特征 xi，针对其它特征的每一种field fj，都会学习一个隐向量


因此，隐向量不仅与特征相关，也与field相关。也就是说，“MovieClass”这个特征与“UserRate”特征和“PlayTimes”特征进行关联的时候使用不同的隐向量，也是FFM中“field-aware”的由来。
通过修改FM的公式，我们可以得出：

例子

FFM其实是在FM的基础上做了一些更加细致化的工作:作者Yuchin认为相同性质的特征归于同一field，而当前特征在不同field上的表现应该是不同的.

比如在广告领域中性别对于广告商(Advertiser)和投放地(Publisher)的作用就是不一样的，比如:


这里的特征被分为了三类，有投放地(Publisher)，广告商(Advertiser)和性别(Gender),如果使用FM来预估这个点击率则是:

这里可以看出FM中隐向量对于不同类别的特征进行组合时都是使用同一个向量，而基于Field-aware的FFM就是对这点进行修改，认为当前向量对于每一个类别都有一个不同的隐向量，比如性别和投放地进行组合的时候使用的隐向量为vMale,G,这样推广开来之后这个问题中FFM的二阶项就可以表述为:

这样,FFM使用通用化的学习公式表达了之后为:

因为FFM的参数空间为nfk,其计算复杂度为O(nk),但是FFM都是在特定的field的中来学习训练隐向量的，所以一般来说:

FFM的改进看上去还是有挺有道理的，但是其实最终实验做出来和FM的效果不相上下。

美团机器学习实践

逻辑回归无法学习到特征间的组合关系，而特征组合关系在推荐和CTR预估中却是比较常见的。在进行点击率预估时，特征通常来自于用户，广告和上下文环境，如果没有对这些特征进行组合，模型就无法学习到所有有用的信息。例如，同一个用户在不同时间或者地点感兴趣的广告是不同的，同一件商品在不同地区的受欢迎程度也是不同的。但是人工对特征组合需要做大量的特征工程工作，对特征做暴力组合模型又太复杂，参数太多。模型训练迭代无论是内存开销还是时间开销都让人很难接受，迭代效果往往也比较差。所以可以用因子分解机和场感知因子分解机来进行自动做特征组合，并且算法效率比较高。

利用模型来做特征组合，很容易想到使用支持向量机的核函数来实现特征之间的交叉。但是多项式核函数的问题就是二次参数过多。设特征维数为n，则二次项的参数数目为n(n+1) / 2，特别是某些广告ID，用户ID类特征，其特征维数可能达到几百万维，这导致只有极少数的二阶组合模式才能找到，所以这些特征组合后得到的特征矩阵就是十分稀疏。而在训练样本不足的时候，特征矩阵的稀疏性很容易导致相关参数准确性较低，导致模型效果不好。而我们可以通过对二次项参数施加某种限制来减少参数的自由度。

因子分解机施加的限制就是要求二次项参数矩阵是低秩的，能够分解为低秩矩阵的乘积。所有二次项参数矩阵W就可以分解为


V的第j列便是第j维特征向量。
因子分解机的模型方程：

在多项式模型中，Whi和Wij是相互独立的，但参数因子化使得XhXi和XiXj的系数分别为<Vh,Vi>和<Vi,Vj>，它们有了共同项Vi。也就是说所有包含Xj的非零组合特征的样本都可以用来学习隐向量Vi，这在很大程度上避免了数据稀疏性造成的影响。

FM可以看做是FFM的特殊情况，是把所有特征都归属到一个场时的场感知因子分解机模型。

FFM的应用

FFM可以自动做特征组合和处理高维稀疏特征，因而它在处理大量离散特征的问题上往往有比较好的效果。使用场感知因子分解机时要注意对连续特征做归一化或离散化。

FM，FFM与其他模型的对比关系。

FM与FFM

场感知因子分解机对因子分解机模型引入场的概念，增加了模型复杂度和模型表达能力。可以将因子分解机理解为场感知因子分解机的特殊简化模式，即所有特征都属于同一个场。

FM与神经网络

神经网络难以直接处理高维稀疏的离散特征，因为这导致神经元的连接参数太多。而因子分解机可以看做对高维稀疏的离散特征做嵌入（Embedding）。

FM和梯度提升树

因子分解机与梯度提升树都可以做特征组合，Facebook就基于梯度提升树学习过特征的组合，梯度提升树可以方便对特征做高阶组合。当数据不是高度稀疏时，梯度提升树可以有效地学习到比较复杂的特征组合；但是在高度稀疏的数据中，特征二阶组合的数量就足以让绝大多数模式找不到样本，因而梯度提升树无法学习到这种高阶组合。

因子分解机与其他模型

因子分解机是一种比较灵活的模型，通过合适的特征变换方式，因子分解机可以模拟二阶多项式核的支持向量机模型、MF模型、SVD++模型等。但SVD++与MF在特征的扩展性上都不如因子分解机，而支持向量机核函数计算复杂度较高。